File system performance may degrade if a large amount of files are stored within a single directory. In general, files may be distributed across multiple directories and sub-directories. However, some file systems place a limitation on the number of sub-directories within a directory and/or a number of files within each directory. Even if the number of files to be stored is known, a solution to optimally sort a file system would be limited to the known number of files, and thus, may prevent scaling of the file system based on a change in file numbers to be sorted.
While reading a directory on a file system, files may be returned in random order. For example, to list the files starting with the prefix “foo,” a complete directory is read. If the directory contains a small number of files, this solution would be sufficient, but for a directory with a large number of files, the process may take a significant amount of time.